package com.wenhao.leetcode.medium;

import com.wenhao.leetcode.structure.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 题目：https://leetcode-cn.com/problems/reorder-list/
 * 重排链表
 * @author Wenhao Tong
 * @create 2021-07-12 17:00
 */
public class LeetCode143 {
    public static void main(String[] args) {

    }

    public void reorderList(ListNode head) {
        if (head == null) {
            return ;
        }
        List<ListNode> list = new ArrayList<>();
        ListNode node = head;
        while (node != null) {
            list.add(node);
            node = node.next;
        }
        int j = list.size() - 1;
        int i = 0;
        while (i < j) {
            list.get(i).next = list.get(j);
            i++;
            if (i == j) {
                break;
            }
            list.get(j).next = list.get(i);
            j--;
        }
        list.get(i).next = null;
    }

    /**
     * 常数级空间复杂度的方法
     */

}
